package ljl.alg.jianzhioffer.round3.easy;

public class _53_search {
    class tedius {
        public int search(int[] nums, int target) {
            int l = binarySearch1(nums, target);
            if (l == -1)
                return 0;
            return binarySearch2(nums, target) - l + 1;
        }

        int binarySearch1(int[] nums, int t) {
            int l = 0, r = nums.length - 1;
            int res = -1;
            while (l <= r) {
                int mid = (l + r) >>> 1;
                if (nums[mid] < t) {
                    l = mid + 1;
                } else {
                    if (nums[mid] == t)
                        res = mid;
                    r = mid - 1;
                }
            }
            return res;
        }
        int binarySearch2(int[] nums, int t) {
            int l = 0, r = nums.length - 1;
            int res = -1;
            while (l <= r) {
                int mid = (l + r) >>> 1;
                if (nums[mid] > t) {
                    r = mid - 1;
                } else {
                    if (nums[mid] == t)
                        res = mid;
                    l = mid + 1;
                }
            }
            return res;
        }
    }

    class lufei1 {

        public int search(int[] nums, int target) {
            return helper(nums, target) - helper(nums, target - 1);
        }
        int helper(int[] nums, int tar) {
            int i = 0, j = nums.length - 1;
            while(i <= j) {
                int m = (i + j) / 2;
                if(nums[m] <= tar) i = m + 1;
                else j = m - 1;
            }
            return i;
        }
    }
}

